class Solution:
  def movingCountWorse(self, m: int, n: int, k: int) -> int:
    max_count = 0
    board = [[0 for j in range(n)] for i in range(m)]

    def dfs(i, j):
      nonlocal max_count, board
      # print('dfs({}, {})'.format(str(i), str(j)))
      # print_board(board)
      # print('----------')
      if not 0 <= i < m or not 0 <= j < n or invalid(i, j, k) or board[i][j] == 1:
        return True
      board[i][j] = 1
      board_count = count_board(board)
      if board_count > max_count:
        max_count = board_count
      res = dfs(i-1, j) and dfs(i, j-1) and dfs(i+1, j) and dfs(i, j+1)
      board[i][j] = 0
      return res

    def count_board(board):
      board_count = 0
      for i in range(m):
        for j in range(n):
          if board[i][j] == 1:
            board_count = board_count + 1
      return board_count
    
    def invalid(i, j, k):
      str_i, str_j = str(i), str(j)
      total_i, total_j = 0, 0
      for i in str_i:
        total_i = total_i + int(i)
      for j in str_j:
        total_j = total_j + int(j)
      if total_i + total_j > k:
        return True
      else:
        return False
    
    # debug method
    def print_board(board):
      for i in range(len(board)):
        for j in range(len(board[0])):
          print(board[i][j], end=' ')
        print()
    
    for i in range(m):
      for j in range(n):
        dfs(i, j)
    return max_count

  def movingCountDFS(self, m: int, n: int, k: int) -> int:
    visited = set()

    def dfs(i, j):
      nonlocal visited
      # print('dfs({}, {})'.format(str(i), str(j)))
      # print_board(board)
      # print('----------')
      if not 0 <= i < m or not 0 <= j < n or invalid(i, j, k) or (i, j) in visited:
        return True
      visited.add((i, j))
      res = dfs(i-1, j) and dfs(i, j-1) and dfs(i+1, j) and dfs(i, j+1)
      return res
    
    def invalid(i, j, k):
      str_i, str_j = str(i), str(j)
      total_i, total_j = 0, 0
      for i in str_i:
        total_i = total_i + int(i)
      for j in str_j:
        total_j = total_j + int(j)
      if total_i + total_j > k:
        return True
      else:
        return False
    
    # debug method
    def print_board(board):
      for i in range(len(board)):
        for j in range(len(board[0])):
          print(board[i][j], end=' ')
        print()
    
    dfs(0, 0)
    return len(visited)

  def movingCountBFS(self, m: int, n: int, k: int) -> int:
    def invalid(i, j, k):
      sum_i = 0
      while i != 0:
        sum_i += i % 10
        i = i // 10
      sum_j = 0
      while j != 0:
        sum_j += j % 10
        j = j // 10
      if k < sum_i + sum_j:
        # print('invalid')
        return True
      else:
        # print('valid')
        return False

    queue, visited = [(0, 0)], set()
    while len(queue) != 0:
      # print('queue', queue)
      i, j = queue.pop(0)
      if not 0 <= i < m or not 0 <= j < n or invalid(i, j, k) or (i, j) in visited:
        continue
      visited.add((i, j))
      queue.append((i-1, j))
      queue.append((i+1, j))
      queue.append((i, j-1))
      queue.append((i, j+1))
    return len(visited)


'''
STATUS: LEARNT
TRIES:  N/A
TIME:   108 MS
MEMORY: 17.5 MB
'''
if __name__ == "__main__":
  solution = Solution()
  print(solution.movingCountBFS(16, 8, 4))